home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / cool / ge_cool.lha / GE_COOL2.1 / src / Tree / N_Node.C < prev    next >
C/C++ Source or Header  |  1992-05-15  |  7KB  |  196 lines
  1. //
  2. // Copyright (C) 1991 Texas Instruments Incorporated.
  3. //
  4. // Permission is granted to any individual or institution to use, copy, modify,
  5. // and distribute this software, provided that this complete copyright and
  6. // permission notice is maintained, intact, in all copies and supporting
  7. // documentation.
  8. //
  9. // Texas Instruments Incorporated provides this software "as is" without
  10. // express or implied warranty.
  11. //
  12.  
  13. #include <cool/N_Node.h>
  14.  
  15. // CoolN_Node -- Simple constructor that allocates enough storage for a vector of
  16. //           pointers to CoolN_Node objects
  17. // Input:    None
  18. // Output:   None
  19.  
  20. template <class Type, int nchild> 
  21. CoolN_Node<Type,nchild>::CoolN_Node<Type,nchild> () {
  22.   for (int i = 0; i < nchild; i++)        // For each pointer in vector
  23.     this->sub_trees[i] = NULL;            // Insure NULL pointer value
  24.   if (this->compare_s == NULL)            // If no compare function
  25.     this->compare_s = &Type##_default_CoolN_Node_compare; // Default
  26. }
  27.  
  28.  
  29. // CoolN_Node -- Simple constructor that allocates enough storage for a vector of
  30. //           pointers to CoolN_Node objects and assigns an initial data value
  31. // Input:    Data slot value
  32. // Output:   None
  33.  
  34. template <class Type, int nchild> 
  35. CoolN_Node<Type,nchild>::CoolN_Node<Type,nchild> (const Type& value) {
  36.   this->data = value;                // Copy initial data value
  37.   for (int i = 0; i < nchild; i++)        // For each pointer in vector
  38.     this->sub_trees[i] = NULL;            // Insure NULL pointer value
  39.   if (this->compare_s == NULL)            // If no compare function
  40.     this->compare_s = &Type##_default_CoolN_Node_compare; // Default
  41. }
  42.  
  43.  
  44. // CoolN_Node -- Copy constructor makes deep copy
  45. // Input:    Reference to CoolN_Node
  46. // Output:   None
  47.  
  48. template <class Type, int nchild> 
  49. CoolN_Node<Type,nchild>::CoolN_Node<Type,nchild> (const CoolN_Node<Type,nchild>& n) {
  50.   for (int i = 0; i < nchild; i++)        // For each pointer in vector
  51.     this->sub_trees[i] = copy_nodes(n.sub_trees[i]); // Deep copy of subnodes
  52.   this->data = n.data;                     // Copy data value
  53.   this->compare_s = n.compare_s;        // Set compare method
  54. }
  55.  
  56.  
  57. // ~CoolN_Node -- Destructor for the CoolN_Node<Type,nchild> class
  58. // Input:     None
  59. // Output:    None
  60.  
  61. template <class Type, int nchild> 
  62. CoolN_Node<Type,nchild>::~CoolN_Node<Type,nchild> () {
  63.   for (int i = 0; i < nchild; i++)        // For each pointer in vector
  64.     delete this->sub_trees[i];            // Invoke destructor
  65. }
  66.  
  67. // is_leaf -- Determine if node has any children
  68. // Input:     None
  69. // Output:    TRUE if no children, else FALSE
  70.  
  71. template <class Type, int nchild> 
  72. Boolean CoolN_Node<Type,nchild>::is_leaf () const {
  73.   for (int i = 0; i < nchild; i++)
  74.     if (this->sub_trees[i])
  75.       return (FALSE);
  76.   return TRUE;
  77. }
  78.  
  79.  
  80. // operator[] -- Overload the brackets operator to provide a mechanism to set
  81. //               and/or get a sub-tree pointer of a node whose zero-relative
  82. //               index is specified from left to right
  83. // Input:        Zero-relative index into vector of sub-tree pointers
  84. // Output:       Reference to a pointer value
  85.  
  86. template <class Type, int nchild> 
  87. inline CoolN_Node_##Type##_##nchild##_p& CoolN_Node<Type,nchild>::operator[] (int index) {
  88. #if ERROR_CHECKING
  89.   if (index >= nchild)                // If index out of range
  90.     this->index_error ("operator[]", index);    // Raise exception
  91. #endif
  92.   return (this->sub_trees[index]);
  93. }
  94.  
  95.  
  96. // operator= -- Overload the assignment operator to copy all values from one
  97. //              node object to another. This routine could potentially result
  98. //              in a complete deep copy, since for each valid sub_tree pointer,
  99. //              a new node is allocated and its sub_tree pointers copied.
  100. // Input:       Reference to CoolN_Node
  101. // Output:      Rererence to updated CoolN_Node
  102.  
  103. template <class Type, int nchild> 
  104. CoolN_Node<Type,nchild>& CoolN_Node<Type,nchild>::operator= (const CoolN_Node<Type,nchild>& n) {
  105.   for (int i = 0; i < nchild; i++) {        // Invoke destructor recursively
  106.     delete this->sub_trees[i];            // for all subnodes
  107.     this->sub_trees[i] = copy_nodes(n.sub_trees[i]); // and make new deep copy
  108.   }
  109.   this->data = n.data;                // Copy data value
  110.   return *this;                    // Return reference
  111. }
  112.  
  113.  
  114. // insert_before -- Insert sub-tree pointer to child before the specified
  115. //                  zero-relative sub-tree index (numbered from left to right)
  116. // Input:           Pointer to child node, zero-relative index
  117. // Output:          TRUE/FALSE
  118.  
  119. template <class Type, int nchild> 
  120. Boolean CoolN_Node<Type,nchild>::insert_before (CoolN_Node<Type,nchild>& n, int index) {
  121. #if ERROR_CHECKING
  122.   if (index < 0 || index >= nchild) {        // If index out of range
  123.     this->index_error ("insert_before", index);    // Raise exception
  124.     return FALSE;                // Return failure status
  125.   }
  126. #endif
  127.   for (int i = nchild-1; i > index; i--)    // For each pointer after index
  128.     this->sub_trees[i] = this->sub_trees[i-1];    // Move up one in vector
  129.   this->sub_trees[i] = &n;            // Pointer to new sub-tree
  130.   return TRUE;                    // Return success status
  131. }
  132.  
  133.  
  134. // insert_after -- Insert sub-tree pointer to child after the specified
  135. //                 zero-relative sub-tree index (numbered from left to right)
  136. // Input:          Pointer to child node, zero-relative index
  137. // Output:         TRUE/FALSE
  138.  
  139. template <class Type, int nchild> 
  140. Boolean CoolN_Node<Type,nchild>::insert_after (CoolN_Node<Type,nchild>& n, int index) {
  141. #if ERROR_CHECKING
  142.   if (index < 0 || index >= nchild) {        // If index out of range
  143.     this->index_error ("insert_after", index);    // Raise exception
  144.     return FALSE;                // Return failure status
  145.   }
  146. #endif
  147.   for (int i = nchild-1; i > index+1; i--)     // For each pointer after index
  148.     this->sub_trees[i] = this->sub_trees[i-1];    // Move up one in vector
  149.   this->sub_trees[i] = &n;            // Pointer to new sub-tree
  150.   return TRUE;                    // Return success status
  151. }
  152.  
  153.  
  154. // copy_nodes -- Copies this node and all its subnodes
  155. // Input:       pointer to node to be copied
  156. // Output:      pointer to new copy of node with all new subnodes.
  157.  
  158. template <class Type, int nchild>
  159. CoolN_Node<Type,nchild>* CoolN_Node<Type,nchild>::copy_nodes (const CoolN_Node<Type,nchild>* n) const {
  160.   if (n == NULL)                
  161.     return NULL;
  162.   CoolN_Node<Type,nchild>* new_n = new CoolN_Node<Type,nchild>; 
  163.   for (int i = 0; i < nchild; i++)        // For each pointer in vector
  164.     new_n->sub_trees[i] = copy_nodes(n->sub_trees[i]); // Deep copy of subnodes
  165.   new_n->data = n->data;                   // Copy data value
  166.   return new_n;                          // Return copied node.
  167. }
  168.  
  169.  
  170. // index_error -- Raise exception invalid index
  171. // Input:         Function name, invalid index
  172. // Output:        None
  173.  
  174. template <class Type, int nchild> 
  175. void CoolN_Node<Type,nchild>::index_error (const char* fcn, int n) {
  176.   //RAISE Error, SYM(CoolN_Node), SYM(Out_Of_Range),
  177.   printf ("CoolN_Node<%s,%d>::%s: Index %d out of range.\n", #Type, nchild, 
  178.       fcn, n);
  179.   abort ();
  180. }
  181.  
  182. // default_CoolN_Node_compare -- Default node comparison function utilizing builtin
  183. //                           less than, equal, and greater than operators
  184. // Input:                    Reference to two Type data values
  185. // Output:                   -1, 0, or 1 if less than, equal to, or greater than
  186.  
  187. template <class Type, int nchild> CoolN_Node {
  188.   int Type##_default_CoolN_Node_compare (const Type& v1, const Type& v2) {
  189.     if (v1 == v2)                // If data items equal
  190.       return 0;                    // Return zero
  191.     if (v1 < v2)                // If this less than data
  192.       return -1;                // Return negative one
  193.     return 1;                    // Else return positive one
  194.   }
  195. }
  196.